//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
//
//
//
// 示例 1：
//
//
//输入：head = [1,2,2,1]
//输出：true
//
//
// 示例 2：
//
//
//输入：head = [1,2]
//输出：false
//
//
//
//
// 提示：
//
//
// 链表中节点数目在范围[1, 10⁵] 内
// 0 <= Node.val <= 9
//
//
//
//
// 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
//
// Related Topics 栈 递归 链表 双指针 👍 1672 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
// 利用数组空间方法
function isPalindrome(head: ListNode | null): boolean {

    const helperArr: number[] = [];
    let curNode: ListNode | null = head;
    while (curNode !== null) {
        helperArr.push(curNode.val);
        curNode = curNode.next;
    }
    let left: number = 0,
        right: number = helperArr.length - 1;
    while (left < right) {
        if (helperArr[left++] !== helperArr[right--]) return false;
    }
    return true;

};

// 反转后半部分链表的方法 无需空间
function isPalindrome2(head: ListNode | null): boolean {

    // 反转后半部分链表
    let node : ListNode | null  = head
    let len : number = 0
    while (node) {
        len++
        node = node.next
    }
    let mid : number = Math.floor(len / 2)
    let midNode : ListNode | null = head
    while (mid--) {
        midNode = midNode.next
    }
    let reversed : ListNode | null
    len % 2 === 1 ? reversed = reverseList(midNode.next) : reversed = reverseList(midNode)
    mid = Math.floor(len / 2)
    while (mid--) {
        if (head.val !== reversed.val) return false
        head = head.next
        reversed = reversed.next
    }
    return true
};
function reverseList(head: ListNode | null): ListNode | null {

    let pre : ListNode | null = null
    let cur : ListNode = head
    while (cur) {
        let nex : ListNode | null = cur.next
        cur.next = pre
        pre = cur
        cur = nex
    }
    // head = pre
    return pre
};
//leetcode submit region end(Prohibit modification and deletion)
